package com.yj.algorithm;

import android.os.Build;

import androidx.annotation.RequiresApi;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 排序算法
 *
 * 1 概述
 * 在计算机科学与数学中，一个排序算法（英语：Sorting algorithm）是一种能将一串资料依照特定排序方式进行排列的一种算法。
 * 最常用到的排序方式是数值顺序以及字典顺序。有效的排序算法在一些算法（例如搜索算法与合并算法）中是重要的，
 * 如此这些算法才能得到正确解答。排序算法也用在处理文字资料以及产生人类可读的输出结果。基本上，
 * 排序算法的输出必须遵守下列两个原则：
 * (1) 输出结果为递增序列（递增是针对所需的排序顺序而言）；
 * (2) 输出结果是原输入的一种排列、或是重组；
 *
 *
 */
public class algorithm5 {

    public static void main(String[] args) {
        int [] numData={4,1,8,3,2,9,5,7,6};
        bubbleSort(numData);
        System.out.println(Arrays.toString(numData));
    }


 /**
   * 冒泡排序
   * 冒泡排序（Bubble Sort）是排序算法里面比较简单的一个排序。它重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，
  *  并一直重复这样的走访操作，直到没有要交换的数据元素为止。
  *
  *  原理
  *  从第一个元素开始，相邻比较，把较大的数值替换到后面，直到最后一个元素，然后再从第一个元素开始，相邻比较，
  *  把较大的数值替换到后面，直到倒数第二个元素，依此类推。
  *
  *  时间复杂度 O(n^2)
  *  空间复杂度 O(1)
  */

    /**
     * 互换顺序
     * @param nums      数组
     * @param srcIndex  源下标
     * @param descIndex 目标下标
     **/
    private static void swap(int[] nums, int srcIndex, int descIndex) {
        int tmp = nums[srcIndex];
        nums[srcIndex] = nums[descIndex];
        nums[descIndex] = tmp;
    }

    /**
     * 冒泡排序
     *
     * @param nums 输入
     **/
    public static void bubbleSort(int[] nums) {

        int length = nums.length;
        if (length > 1) {
            for (int i = nums.length - 1; i > 0; i--) {
                // 如果数组只有1位则直接返回
                boolean doSort = false;
                for (int j = 0; j < i; j++) {
                    if (nums[j] > nums[j + 1]) {
                        swap(nums, j, j + 1);
                        doSort = true;
                    }
                }

                // 如果未进行过顺序调整，则表示前面的元素均为有序元素
                if (!doSort) {
                    break;
                }
            }
        }
    }


    /**
     * 选择排序
     *
     * 找到数组中的最小值放在第一位，次小的放在第二位，依此类推
     *
     * 时间复杂度 O(n^2)
     * 空间复杂度 O(1)
     */

    public static void selectionSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int index = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[index])
                    index = j;
            }
            swap(array, index, i);
//            int temp = array[index];
//            array[index] = array[i];
//            array[i] = temp;
        }
    }

    /**
     *
     * 插入排序
     *
     * 假设第一个元素是有序数组，把第二个元素放在这个“有序数组”的正确位置，然后第一、二个元素变成有序数组，
     * 把第三个元素放到这个有序数组的正确位置，依此类推
     * 时间复杂度 O(n^2)
     * 空间复杂度 O(1)
     */

    public  static  void insertSort(int [] array){
        //外循环规定从第二个元素开始，将元素插入到已排行的数组中
        for(int i=1;i<array.length;i++){
            //用key来表示插入的元素，若直接用array[i]表示，array[j+1]操作会更改array[i]的值
            int key = array[i];
            //j表示从已排行好序的数组的最右边开始比较
            int j=i-1;
            while (j>=0&&key<array[j]){
                //若插入的元素小，则将被比较的元素后移一位
                array[j+1] = array[j];
                j--;
            }
            //此时的array[j]代表者被插入元素左边相邻的那个元素
            array[j+1] = key;
        }
    }

    /**
     * 希尔排序
     *
     * 把数组分成length/2组，然后各组各自排序，然后把数组分成length/2/2组，然后各组各自排序，
     * 然后继续分成length/2/2/2组进行各自排序，直到length/2/2.../2=1
     *
     * 时间复杂度 O(n log n)
     * 空间复杂度 O(1)
     *
     */
    public  static  void shellSort(int [] array){
      //设置gap为增量
      int addValue=2;
      int gap=array.length / addValue;
      //外循环：增量gap每次变小，直到为1
      for(; gap>0; gap/=addValue){
          //内循环：进行插入排序，从每个分组的第gap个元素开始，而不是从它的第一个元素开始
          for(int i=gap;i<array.length;i++){
              //如果小于前一个元素，进行交换，把小的换到前面来
              if(array[i]<array[i-gap]){
                  //保存小的元素
                  int temp=array[i];
                  //记录前一个比它大的角标
                  int k=i-gap;
                  //如果改组元素中，前几个元素都比array[i]大。则执行后移，把比array[i]大的都移动到array[i]后面
                  while (k>=0&&array[k]>temp){
                      array[k+gap] = array[k];
                      k-=gap;
                  }
                  //此时array[k]<array[i],array[i]放到array[k]右边
                  array[k+gap] = temp;
              }
          }
        }
    }

    /**
     * 归并排序
     * 把数组分成平分成两组，再把分成的两组再各分成两组总共四组，再把分成的四组再各分成两组总共8组，当小分组中只有1个元素时开始对小分组排序，
     * 排序完成后合入父分组中再排序，直到合成的分组为原始分组时，排序完成
     *
     * 时间复杂度 O(n log n)
     * 空间复杂度 O(n)
     *
     * 归并排序是一种分治策略的排序算法，它的核心思想是将数组分成两个子数组，递归地对子数组进行排序，然后将排序好的子数组合并起来，
     * 最终得到有序的数组。归并排序的关键步骤包括：
     * 分割阶段： 将数组分成两个子数组，通常是平均分割。
     * 递归排序： 递归地对左右两个子数组进行排序。
     * 合并阶段： 将排好序的子数组合并成一个新的有序数组
     */

    //归并排序
    public static  void mergeSort(int [] arr){
      //针对特殊情况，数组为空或只有一个元素时，无需要排序
      if(arr==null||arr.length<=1){
          return;
      }
      //创建一个临时数组用于归并操作
      int [] temp=new int[arr.length];

      //调用实际的排序方法，传入数组，左边界，右边界和临时数组

      sort(arr,0,arr.length-1,temp);
    }

    //归并排序的核心排序方法(递归调用的方法)
    public  static  void sort(int [] arr,int left,int right,int [] temp){
        //递归终止的条件
        if(left<right){
            //计算中间位置分割的下标
            int mid=(right+left)/2;
            //递归对左半部分进行排序
            sort(arr,left,mid,temp);
            //递归对右半部分进行排序
            sort(arr,mid+1,right,temp);
            //合并
            merge(arr,left,mid,right,temp);
        }
    }

    //归并排序的核心归并方法
    public  static  void merge(int [] arr,int left,int mid,int right,int [] temp){
        int i=left;
        int j=mid+1;
        int k=left;
        //比较左右两部分的元素，并将较小的元素放入临时数组
        while (i<=mid&&j<=right){
            if(arr[i]<=arr[j]){
                temp[k++]=arr[i++];
            }else{
                temp[k++]=arr[j++];
            }
        }
        //如果右边元素先放完，则将左边剩余的元素逐个放入临时数组中
        while (i<=mid){
            temp[k++]=arr[i++];
        }
        //如果左边元素先放完，则将右边剩余的元素逐个放入临时数组中
        while (j<=right){
            temp[k++]=arr[j++];
        }
        //将临时数组的结果复制回原数组
        for(int l=left;l<=right;l++){
            arr[l]=temp[l];
        }
    }

    /**
     * 快速排序
     * 	选定最后一个元素作为分界值，迭代数组，把小于分界值的往前排，大于分界值的往后排，使得分界值前的元素小于分界值，
     * 	分界值后的元素大于等于分界值，然后把分界值左右分成两个小数组，重复分界处理，分界完后再拆分成小数组，直到拆无可拆时，数据已有序
     *
     * 时间复杂度 O(n log n)
     * 空间复杂度 O(log n)
     */

    public static  void quickSort(int [] a,int low,int high){
        //改值定义了从哪个位置开始分割序列
        int pivot;
        //当high-low大于某一值时适合快速排序
        if(low<high){
          //partition方法对序列进行排序
          pivot=partition(a,low,high);
          //分割两个序号继续进行快速排序
          quickSort(a,low,pivot-1);
          quickSort(a,pivot+1,high);
        }
    }

   public static  int partition(int [] a,int low,int high){
        //取每个序列的第一个值作为基准值
       int pivotkey=a[low];
       while (low<high){
           //从序列的右边开始往左遍历，知道找到小于基准值的元素
           while (high>low&&a[high]>=pivotkey){
               high--;
           }
           //将元素直接赋予给左边第一个，即pivotkey所在的位置
           a[low] = a[high];
           //从序列的左边边开始往右遍历，直达找到大于基准值的元素
           while (high>low && a[low]<=pivotkey){
               low++;
           }
           //此时的a[high]<pivotkey,已经被赋予到左边，所有可以将元素赋予给a[high]
           a[high]=a[low];
       }
       //最后的low是基准值所在的位置
       a[low] = pivotkey;
       return low;
   }

    /**
     * 堆排序
     * 先把数组分成一个堆（平衡二叉树），从最后一个树叶开始（最下一层、最右边），把较大的元素往树枝移，移完一轮后，
     * 把第一个元素跟最后一个元素替换，使得最后一个元素为数组中的最大值；然后，把最后一个元素排除，重复前面步骤，直到迭代到第一个元素
     *
     * 时间复杂度 O(n log n)
     * 空间复杂度 O(1)
     */
    //声明全局变量，用于记录数组array的长度;
    static int len;

    public static int [] heapStor(int [] array){
        len=array.length;
        if(len<1) return array;
        //1.构建一个最大堆
        buildMaxHeap(array);
        //2.循环将堆首位(最大值)与末位交换，然后在重新调整最大堆
        while (len>0){
            swap(array,0,len-1);
            len--;
            adjustHeap(array,0);
        }
        return  array;
    }

    //建立最大堆
    public static void buildMaxHeap(int [] array){
        //从最后一个非叶子节点开始向上构造最大堆
        for(int i=(len/2-1);i>=0;i--){
            adjustHeap(array,i);
        }
    }

    //调整使之成为最大堆
    public static void adjustHeap(int [] array,int i){
        int maxIndex=i;
        //如果有左子树，且左子树大于父节点，则将最大指针指向左子树
        if(i*2<len && array[i*2+1] > array[maxIndex])
            maxIndex=i*2;
        //如果有右子树，且右子树大于父节点，则将最大指针指向右子树
        if(i*2+1<len&&array[i*2+1]>array[maxIndex])
            maxIndex=i*2+1;
        //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置
        if(maxIndex!=i){
            swap(array,maxIndex,i);
            adjustHeap(array,maxIndex);
        }
    }
    /**
     * 基数排序
     * 先找出数组中最长的数（因为会包含正数、负数，所以是最长而不是最大），然后先按个位，分成十个小数组，把这十个小数组合并，接下来按十位，
     * 分成十个小数组，再合并，依此类推，最后得到有序数组
     *
     * 时间复杂度 O(nk)
     * 空间复杂度 O(n+k)
     *
     * 基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数
     * 基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，
     * 先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的
     *
     * 取得数组中的最大数，并取得位数；
     * arr为原始数组，从最低位开始取每个位组成radix数组；
     * 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
     */

    public static int [] radixSort(int [] array){
        if(array==null||array.length<2)
            return array;
        //1.先算出最大数的位数
        int max=array[0];
        for(int i=1;i<array.length;i++){
            max= Math.max(max,array[i]);
        }
        int maxDigit = 0;
        while (max!=0){
            max/=10;
            maxDigit++;
        }
        int mod=10,div=1;
        ArrayList<ArrayList<Integer>> bucketList =new ArrayList<>();
        for(int i=0;i<10;i++)
            bucketList.add(new ArrayList<>());
        for(int i=0;i<maxDigit;i++,mod*=10,div*=10){
                for(int j=0;j<array.length;j++){
                    int num=(array[j]%mod)/div;
                    bucketList.get(num).add(array[j]);
                }
                int index = 0;
                for(int j=0;j<bucketList.size();j++){
                    for(int k=0;k<bucketList.get(j).size();k++)
                       array[index++]=bucketList.get(j).get(k);
                    bucketList.get(j).clear();
                }
          }
        return  array;
    }

    /**
     * 计数排序
     *
     * 建一个空数组，数组长度可选为数组的最大值+1，或者最大值-最小值+1，然后迭代数组，把数组的值作为新数组的索引，计算每个元素出现的次数，
     * 最后迭代新数组，依序把新数组的索引写入原始数组，即可得到有序数组
     *
     * 时间复杂度 O(n+k)
     * 空间复杂度 O(k)
     */
    @RequiresApi(api = Build.VERSION_CODES.N)
    public static void countingSort(int[] arr){
        System.out.println("原始数组："+ Arrays.toString(arr));
        //获取排序数组的长度
        int len=  arr.length;
        //获取数组最大元素
        int max = Arrays.stream(arr).max().getAsInt();
        //获取数组最小元素
        int min = Arrays.stream(arr).min().getAsInt();
        //计算计数数组的长度
        int rang = max-min+1;
        //创建计数数组
        int count[] = new int[rang];
        //创建排序后的目标数组
        int result[] = new int[len];
        //计数:统计每个元素出现的次数
        for(int i = 0; i < len; i++){
            count[arr[i]-min]++;
        }
        System.out.println("计数数组："+ Arrays.toString(count));
        //累计计数:计算每个元素在排序后数组中的位置
        for(int j = 1 ;j < rang; j++){
            count[j]+=count[j-1];
        }
        System.out.println("累计计数数组："+ Arrays.toString(count));
        //排序：根据累计计数数组将元素放置到正确的位置
        for(int k = len -1 ; k >= 0; k--){
            result[count[arr[k] - min] -1] = arr[k];
            count[arr[k] - min]--;
        }
        System.arraycopy(result, 0, arr, 0, len);
        System.out.println("排序完成的数组："+ Arrays.toString(arr));
    }
    /**
     *  桶排序
     *  将数组按一定的规则，分到多个桶里面，然后对桶里面的小数组排序，最后再组合即可得到有序数组；分桶的规则可以是元素除以10的n次方、2的n次方、
     *  （数组的最大值-最小值)/2等，分桶后会把较小的值放前面的桶，较大的值放后面的桶；桶内排序可以用其他排序算法，也可以继续使用桶排序
     *
     * 时间复杂度 O(n+k)
     * 空间复杂度 O(n+k)
     */
    public static  void countSort(int [] arr){
        if(arr==null||arr.length<2){
            return;
        }
        //找到数组中最大的数
        int max=Integer.MIN_VALUE;
        for(int i=0;i<arr.length;i++){
            max=Math.max(max,arr[i]);
        }
        //实例化一组桶
        int [] bucket=new int[max+1];
        //把数组中的数放到自己的桶中
        for(int i=0;i<arr.length;i++){
            bucket[arr[i]]++;
        }
        //按照桶的顺序把数倒出来
        int i=0;
        for(int j=0;j<bucket.length;j++){
            while (bucket[j]-->0){
                arr[i++]=j;
            }
        }
    }

    /**
     *
     */
}
